//
//  MinArray.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/22.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 11. 旋转数组的最小数字  和154题一样。154题标识为困难难度

import UIKit

/*
 剑指 Offer 11. 旋转数组的最小数字
 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

 示例 1：

 输入：[3,4,5,1,2]
 输出：1
 示例 2：

 输入：[2,2,2,0,1]
 输出：0
 注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
 */

class MinArray: NSObject {
    
    //直接使用二分法
    func minArray(_ numbers: [Int]) -> Int {

        var left = 0
        var right = numbers.count - 1
        
        while left < right {
            let middle = left + (right-left)/2
            let middleNum = numbers[middle]
            
            let rightNum = numbers[right]
            
            if  middleNum < rightNum{
                right = middle
            }else if middleNum > rightNum{
                left = middle + 1
            }else if middleNum == rightNum{
                /*
                 由于重复元素的存在，我们不能确定numbers[middle]究竟在目标最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分。
                 我们唯一可以知道的是，由于它们的值相同，所以无论numbers[right]是不是最小值，
                 都有一个它的“替代品”numbers[middle]，因此我们可以忽略二分查找区间的右端点
                 */
                right -= 1
            }
            
        }
        return numbers[left]
    }
}
